import java.util.Deque;
import java.util.LinkedList;

// 力扣117. 填充每个节点的下一个右侧节点指针 II
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};



class Solution {
    public Node connect(Node root) {
        if(root == null){
            return root;
        }
        Deque<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            Node prev = queue.peek();
            for(int i=0;i<size;i++){
                Node cur = queue.poll();
                if(prev!=cur){
                    prev.next = cur;
                    prev = prev.next;
                }
                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if(cur.right!=null){
                    queue.add(cur.right);
                }
            }
            prev.next = null;
        }
        return root;
    }
}




// 力扣112. 路径总和
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution1 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return searchPath(root,targetSum,0);
    }
    public boolean searchPath(TreeNode root,int targetSum,int path){
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null && path + root.val == targetSum){
            return true;
        }
        boolean leftTree = searchPath(root.left,targetSum,path + root.val);
        boolean rightTree = searchPath(root.right,targetSum,path + root.val);
        return leftTree||rightTree;
    }
}




// 力扣129. 求根节点到叶节点数字之和
class Solution2 {
    private int sum = 0;

    public int sumNumbers(TreeNode root) {
        searchForSum(root, 0);
        return sum;
    }

    public void searchForSum(TreeNode root, int path) {
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            sum += (path * 10 + root.val);
            return;
        }
        searchForSum(root.left, path * 10 + root.val);
        searchForSum(root.right, path * 10 + root.val);
        return;
    }
}



// 力扣173. 二叉搜索树迭代器
class DLinkedList {
    int val;
    DLinkedList next;
    public DLinkedList(int val) {
        this.val = val;
    }
}

class BSTIterator {
    private DLinkedList head;
    private DLinkedList current;

    public BSTIterator(TreeNode root) {
        head = new DLinkedList(-1); // 哑节点
        DLinkedList[] tailRef = new DLinkedList[]{head}; // 使用数组传递引用
        inorderTraversal(root, tailRef);
        current = head;
    }

    public int next() {
        if (hasNext()) {
            current = current.next;
            return current.val;
        }
        return -1; // 按照原代码逻辑返回-1，但更好的做法是抛出异常
    }

    public boolean hasNext() {
        return current.next != null;
    }

    private void inorderTraversal(TreeNode node, DLinkedList[] tailRef) {
        if (node == null) return;

        inorderTraversal(node.left, tailRef);

        // 添加当前节点到链表
        DLinkedList newNode = new DLinkedList(node.val);
        tailRef[0].next = newNode;
        tailRef[0] = newNode; // 更新尾节点

        inorderTraversal(node.right, tailRef);
    }
}
